package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-11 14:15
 */
public class AK56合并区间 {
    public static void main(String[] args) {
        int[][] arrays = {{1,3},{2,6},{8,10},{15,18}};
        arrays = merge(arrays);
        PrintUtil.print(arrays);
    }

    /**
     * 1.根据起始值进行排序 从小到大排序
     * 2.合并新数组
     *
     * 第一遍解题没有考虑到更深的逻辑-XXX解了2个多小时 效率都没提上去
     *
     * @param intervals
     * @return
     */
    public static int[][] merge(int[][] intervals) {
        sort(intervals);

        int[][] intervalsNew = new int[intervals.length][2];
        intervalsNew[0] = intervals[0];

        int length = 0;
        for (int i = 1; i < intervals.length; i++) {
            int[] array = intervals[i];
            //此处不需要从第一个数比 直接跟最后一个数比就可以了
            if (array[0] <= intervalsNew[length][1] && array[1] >= intervalsNew[length][1]) {
                //如果区间部分重合 则进行替换
                intervalsNew[length][1] = array[1];
            } else if(array[0] > intervalsNew[length][1]){
                //如果区间不重合 则将其加入数组下一个值中
                intervalsNew[length + 1] = array;
                length++;
            }
        }
        length++;
        int[][] intervalsNew2 = new int[length][2];
        for (int i = 0; i < length; i++) {
            intervalsNew2[i] = intervalsNew[i];
        }
        return intervalsNew2;
    }

    public static int[][] sort(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        return intervals;
    }


    //不需要提前排序 但是耗时很高 因为时间复杂度为n*n
    public static int[][] merge2(int[][] intervals) {
        int length = intervals.length;
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                int[] array1 = intervals[i];
                int[] array2 = intervals[j];
                int data10 = array1[0];
                int data11 = array1[1];
                int data20 = array2[0];
                int data21 = array2[1];
                if (data10 == -1) {
                    break;
                }
                if (data20 == -1) {
                    continue;
                }

                //如果数组1包含数组2 或数组2包含数组1 全包含 则丢弃被包含的数组
                if (data10 <= data20 && data11 >= data21) {
                    intervals[j] = new int[]{-1, -1};
                    length--;
                } else if (data20 <= data10 && data21 >= data11) {
                    //如果数组1包含数组2 或数组2包含数组1 全包含 则丢弃被包含的数组
                    intervals[i] = array2;
                    intervals[j] = new int[]{-1, -1};
                    length--;
                    i--;
                    break;
                } else if (data10 <= data20 && data11 >= data20) {
                    //如果半包含则替换
                    intervals[i][1] = data21;
                    intervals[j] = new int[]{-1, -1};
                    length--;
                    i--;
                    break;
                } else if (data10 <= data21 && data11 >= data21) {
                    //如果半包含则替换
                    intervals[i][0] = data20;
                    intervals[j] = new int[]{-1, -1};
                    length--;
                    i--;
                    break;
                } else if ((data20 == -1 && data21 == -1) || (data10 == -1 && data11 == -1)) {
                    length--;
                } else if (data10 > data20) {
                    intervals[i] = array2;
                    intervals[j] = array1;
                }

            }
        }
        int[][] arrays = new int[length][2];
        int count = 0;
        int i = 0;
        while (count < length) {
            if (intervals[i][0] != -1 || intervals[i][1] != -1) {
                arrays[count] = intervals[i];
                count++;
            }
            i++;
        }

        return arrays;
    }
}
